// https://www.lintcode.com/problem/jump-game/description

class Solution {
public:
    /**
     * @param A: A list of integers
     * @return: A boolean
     */
    // 法一：O(N^2) dp
    // bool canJump(vector<int> &A) {
    //     vector<bool> res(A.size(), false);
    //     res[0] = true; // 注意
    //     for (int i = 0; i < A.size(); ++i) {
    //         if (res[i]) {
    //             for (int j = 1; j <= A[i]; ++j) {
    //                 if (i + j < A.size()) res[i + j] = true;
    //             }
    //         }
    //     }
    //     return res.back();
    // }

    bool canJump(vector<int>& nums) {
        int n = nums.size();
        vector<bool> rec(n, false);
        rec[0] = true;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (rec[j] && j + nums[j] >= i) rec[i] = true;
            }
        }
        return rec[n - 1];
    }

    // 法二：O(N) 贪心
    bool canJump(vector<int> &A) { 
        int farthest = 0;
        for (int i = 0; i < A.size(); ++i) {
            if (i <= farthest && i + A[i] > farthest) farthest = i + A[i];
        }
        return farthest >= A.size() - 1;
    }
};